Remote access and retrieval of data and information are becoming more desirable and common in both consumer and business environments. As data and information transfer is becoming more and more voluminous and complex, using traditional data links such as voice-band modems is too slow in speed. For example, the use of the Internet to locate and access information is increasing daily, but the retrieval of typical graphics, video, audio, and other complex data forms is generally unsatisfactorily slow using conventional voice-band modems. In fact, the slow rate of existing dial-up analog modems frustrates users, and commerce and interaction using the Internet would have been even higher were it not for the unacceptable delays associated with present day access technology. The ability to provide such desired services as video on demand, television (including HDTV), video catalogs, remote CD-ROM's, high-speed LAN access, electronic library viewing, etc., are similarly impeded by the lack of high speed connections.
Since copper lines are widely available and developed, solutions to the high speed access problem have been focused on improving the performance of voice-band modems, which operate at the subscriber premises end over a 3 kHz voice band and transmit signals through the public switching telephone network (PSTN). The phone company network treats them exactly like voice signals. These modems presently transmit up to 33.6 kb/s over 2-wire telephone line, even though the practical speed was 1.2 kb/s only twenty years ago. The improvement in voice band-modems over the past years has resulted from significant advances in algorithms, digital signal processing, and semiconductor technology. Because such modems are limited to voice bandwidth (3.0 kHz), the rate is bound by the Shannon limit, around 30 kb/s. A V.34 modem, for example, achieves 10 bits/Hz, a figure that approaches the theoretical Shannon limits. There is a considerable amount of bandwidth available in copper lines, however, that has gone unused by voice-band modems, and this is why a proposal known as Asymmetric Digital Subscriber Loop (ADSL) was suggested in the industry as a high-speed protocol/connection alternative. The practical limits on data rate in conventional telephone line lengths (of 24 gauge twisted pair) vary from 1.544 Mb/s for an 18,000 foot connection, to 51.840 Mb/s for a 1,000 foot connection. Since a large proportion of current telephone subscribers fall within the 18,000 foot coverage range, ADSL can make the current copper wire act like a much "bigger pipe" for sending computer bits and digital information (like movies and TV channels), while still carrying the voice traffic. For example, an ADSL modem can carry information 200 times faster than the typical voice band modem used today.
ADSL is "asymmetric" in that more data goes downstream (to the subscriber) than upstream (back from the subscriber). The reason for this is a combination of cost, cross-talk, speed demands, and performance. For example, twisted pair wiring coupling increases with the frequency of the signal. If symmetric signals in many pairs are used within a cable, the data rate and line lengths become significantly limited by the coupling noise. Since the preponderance of target applications for digital subscriber services is asymmetric, asymmetric bit rate is not perceived to be a serious limitation at this time. Therefore, the ADSL standard proposes up to 6 Mb/s for downstream, and up to 640 kb/s for upstream. For example, video on demand, home shopping, Internet access, remote LAN access, multimedia access, and specialized PC services all feature high data rate demands downstream, to the subscriber, but relatively low data rates demands upstream. The principal advantage is that all of the high speed data operations take place in a frequency band above the voice band, leaving Plain Old Telephone Service (POTS) service independent and undisturbed, even if an ADSL modem fails. ADSL further provides an economical solution for transmission of high bandwidth information over existing copper line infrastructures.
Specifically, the T1E1.413 ADSL standard divides the available transmission bandwidth into two parts. At the lower 4 kHz band, ordinary (POTS) is provided. The bulk of the rest bandwidth in the range from 4 kHz to about 1 MHz is for data transmission in the downstream direction, which is defined to be from the exchange to the subscriber. The upstream control channel uses a 160 kHz band in between. The signals in each channel can be extracted with an appropriate band-pass filter.
According to the T1E1.413 ADSL standard, a line code scheme called Discrete Multi-Tone (DMT) is used, which divides the spectrum from 4 kHz to 1.1 MHz into 255 4.3125 kHz channels. Each channel uses Quadrature Amplitude Modulation (QAM) to carry 2 to 15 bits/QAM symbol. This results essentially in overall performance which is equivalent to around two hundred V.34 modems used in parallel on the same line. Because each channel can be configured to a different bit rate according to the channel characteristics, it can be seen that DMT is inherently "rate-adaptive" and extremely flexible for interfacing with different subscriber equipment and line conditions. In typical DMT implementations, such as shown in U.S. Pat. No. 5,479,447 to Chow et. al., transmission power to the individual channels is initially configured based on the noise power and transmission loss in each band. In this way, channels with less noise and attenuation can carry larger amounts of data, while poorer sub-channels can be configured to carry fewer bits and can even be shut down entirely. U.S. Pat. No. 5,596,604 to Cioffi et. al. shows that it is known to store relevant information for each DMT channel in a so called Bit & Energy Table. It is further known (U.S. Pat. No. 5,400,322 to Hunt et. al.) that line conditions can vary after initialization because of temperature fluctuations, interference, etc., and this can affect both the error rate and maximum data throughput. By measuring the quality of each sub-channel on an ongoing basis, an "updated" Bit & Energy Table is maintained to adaptively configure the system for maximum data throughput or error performance. In normal applications, if the quality of any particular channel degrades to the point where the error performance of the system is compromised, one or more bits on that sub-channel are automatically moved to a sub-channel that can support additional bits.
To maximize the overall bit rate from the given channel characteristics and to achieve the target bit error rate (BER), a DMT codec needs to determine the number of bits for each QAM channel and allocate the output power within the standard's output power spectrum requirements. Since the channel characteristics may vary as a function of time, the results of this bit allocation and power allocation process need to be updated constantly. The process of determining and dynamically adapting the optimal bit capacity output power for each sub-channel is generally referred to in the art as bit/energy loading and bit fine tuning respectively.
A good combined energy loading and bit fine tuning algorithm can optimize the system performance, as measured by considerations such as the overall data throughput rate, power margin, bit-error rate, and compliance with the T1E1.413 ADSL standard. Since there is a complex and nonlinear dependence between the power margin, bit allocation, and energy loading for each sub-channel, the computation may not necessarily converge. Therefore, it is critical for the energy loading and bit-fine tuning to rapidly converge and achieve the optimum bit allocation (i.e. maximum power margin) at the given target bit rate. Furthermore, the computation should be simple to minimize the computation time or hardware requirements.
The primary problem of the energy loading and bit allocation is explained below. First, at the given channel characteristic (i.e. channel transfer function and noise spectrum density), power margin, and bit error rate, the number of bits that can be used in QAM modulation is well known in the art and can be expressed as: ##EQU1## where E.sub.i is the energy (power/Hz) allocated to sub-channel i, H.sub.i is the value of the transfer function at the center frequency of sub-channel i, .gamma..sub.m is the power margin, .gamma..sub.b is the power gap required to achieve the specified bit error rate (e.g. 9.8 dB for BER of 10.sup.-7 in the theoretical limit), and N.sub.i is the noise power spectrum density at the center frequency of sub-channel i. Since b.sub.i in practice needs to be an integer, the T1E1.413 standard permits a .+-.3 dB variation of the output energy E.sub.i with respect to -40 dBm/Hz. From the above equation, the energy loading algorithm and bit allocation problem is to find a set of E.sub.i within the T1E1.413 requirements that can maximize the power margin .gamma..sub.m and at the same time achieve the target bit rate ##EQU2##
A variety of bit and energy loading methods are known in the art. These include generally the following: (A) a system devised by Hughes-Hartogs, and described in U.S. Pat. No. 4,731,816. In this scheme, bit loading is performed incrementally, i.e., one bit at a time, until the desired bit rate is achieved. Each new bit is added to the sub-channel that requires the least amount of incremental power to sustain such bit. This algorithm was developed primarily for voice-grade modems, however, and because of its computationally complexity is not well suited for ADSL applications. Because this algorithm also inherently requires an integer number of bits, it is difficult and inefficient to extend its use to other environments that do not require bit granularity, such as Trellis coding. In addition, this algorithm requires a large amount of hardware memory space for the various power matrices associated with the sub-channel bit allocations, which makes this approach undesirable for this reason as well. (B) a "water pouring" method which basically inverts the SNR curve for the channel, and then "pours" bits into each sub-channel. At a given total output power, this method allocates equal energy for each sub-channel. The difference between the output energy and the inverted SNR in dB gives the number of bits that can be sent as can be seen from Equation (1). Although this algorithm yields the optimum theoretical performance, it is not applicable in practice. One simple reason is the bits allocated for each channel may not be integer and may not fall into the range from 2 to 15 as specified by the T1E1.413 standard. (C) an "iterative" method which updates the power margin and bit allocation alternatively. A particular implementation of the iterative approach is described in "A Practical Discrete Multi-tone Transceiver Loading Algorithm for Data Transmission over Spectrally Shaped Channels," by Peter S. Chow et. al., appearing in IEEE Transactions on Communications, pp. 773-775, v.43, nos. 2, 3, 4 (February/March/April 1995) (hereinafter "Chow article"). It is generally perceived in the art that the iterative approach provides the most promise for achieving the greatest overall system performance for ADSL.
The Chow article, which is incorporated by reference herein, sets out a bit and energy loading algorithm based on the power for each sub-channel. In general terms, the Chow article algorithm first starts off by assuming an initial power margin of zero dB, i.e., that each sub-channel can be filled to its maximum capacity. It then computes the bit capacity (b.sub.i) for each sub-channel based on the observed signal to noise ratio, and the system performance margin. These respective capacities are rounded off as explained above to create integer based bit capacities designated ROUND(b.sub.i). The individual integer sub-channel bit capacities ROUND (b.sub.i), as well as the rounding differences (i.e., ROUND[b.sub.i ]-b.sub.i) are stored in arrays. Then, a simple summation is done over the individual sub-channel capacities (ROUND [b.sub.i ]) to determine the total bits per multi-tone symbol, B.sub.total. The current system performance margin for each channel, .gamma..sub.m,current (dB), is re-computed based on the previous system performance margin, .gamma..sub.m,previous (in dB and is initially zero) according to EQU .gamma..sub.m,current =.gamma..sub.m,previous +10.times.log.sub.10 (2.sup.(B.sbsp.total.sup.-B.sbsp.target.sup.)/N.sbsp.CH)
where B.sub.total the is actual total bits per multi-tone symbol, B.sub.target is the desired target bits per multi-tone symbol, and N.sub.ch is the number of channels used.
The power margin is then used to re-calibrate the sub-channel bit capacities, and the whole process repeats (iterates) until a steady state solution is achieved that meets the necessary system performance margin and bit target rates. While this scheme works well in many applications, we have discovered that it suffers from a number of drawbacks, including the fact that for many real-world line environments, the above algorithm fails to "converge"; in other words, despite repeated iterations, the new calculated system performance margin and overall bit rate throughput deviate from the targeted rates. This is illustrated in FIG. 1A. In fact, in many situations, the algorithm causes the system performance margin and bit throughput variations to increase, rather than decrease, with each iteration. This phenomenon, which has been verified experimentally using simulation software known as MATLAB, is depicted generally in FIG. 1A. As can be seen there, for a typical ADSL application where the targeted bits per multi-tone symbol is 1000 bits/symbol, the actual bits achieved deviates significantly from iteration to iteration, and in fact becomes worse as the process continues. FIG. 1B shows that for a smaller target bits of 700 bits/symbol, the prior art algorithm fails to even come close, and at iteration No. 19 it deviates by more than 70% (1195 versus 700) from the required targeted rate. These deviations from the targeted bit rate are obviously highly undesirable, as they compromise system integrity, and cause significant system performance degradation. Moreover, as seen in FIG. 1C, this process does not converge after a large number of iterations, as it supposed to do, and consequently the continuing computations waste valuable system resources. Consequently, the prior art cannot achieve a solution that is satisfactory across all potential operating conditions.
Even though the energy loading and bit allocation can be optimally done at the beginning of the call setup (or during an initialization process for an always on connection) there are nevertheless occasions and circumstances that may call for power margin and/or overall data rate updates to maintain optimum system performance. The occasions and circumstances include the changes of the overall channel characteristics and the required target bit rate. For this reason, it is also known in the art that a bit "fine tuning" process is needed to adapt the system performance over a wider operating range.
The prior art bit fine tuning processes described in the literature to date are adequate but are subject to a couple of deficiencies. For example, in the Chow article referenced above, the bit fine tuning process operates basically as follows: if the achieved overall bit rate B.sub.total exceeds the target bit rate, B.sub.target, the array containing the differences in the rounding operation (i.e., the ROUND[b.sub.i ]-b.sub.i) values) is examined. The sub-channel with the smallest difference is located, and a single bit is subtracted from that sub-channel, reducing B.sub.total by one. This process is repeated (i.e., the next smallest difference is now located) until B.sub.total is equal to B.sub.target. For the case where B.sub.total is below the target bit rate, B.sub.target, the sub-channel with the greatest difference is located, and a single bit is added to that sub-channel, increasing B.sub.total by one. As before, this process is repeated (i.e., the next largest difference is now located) until B.sub.total is equal to B.sub.target. This approach is simple, but its computational complexity is a direct function of the number of bits to be added or subtracted to achieve the target bit rate. Furthermore, this technique does not consider the power margin of the sub-channel, and for that reason, it is unable to approach the optimum performance. Finally, the bit fine tuning process described in Chow is tied to the initial bit and energy loading algorithm, making it difficult for it be extended easily to other bit and energy loading implementations. Accordingly, all the prior art described immediately above have a number of drawbacks and shortcomings which result in ADSL systems having reduced performance levels or requiring extensive computations.